package LeetCode_105;

import java.util.*;
/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/30 15:30
 */
class Solution {
    private List<Integer> toList(int[] array) {
        List<Integer> list = new ArrayList<>();
        for (int e : array) {
            list.add(e);
        }
        return list;
    }
    //链表方法
    // 少用数组，多用 List
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        List<Integer> preorderList = toList(preorder);
        List<Integer> inorderList = toList(inorder);

        return build(preorderList, inorderList);
    }

    private TreeNode build(List<Integer> preorder, List<Integer> inorder) {
        if (preorder.size() == 0) {
            // 说明前序序列中一个元素都没有，是空树
            return null;
        }

        // 如果愿意，preorder.size() == 1 的情况也可以特殊处理

        // 1. 先确定根的值
        int rootVal = preorder.get(0);  // size > 0
        // 2. 确定 rootVal 在中序中的下标，也就是左子树的结点个数
        int leftSize = inorder.indexOf(rootVal);
        int rightSize = inorder.size() - 1 - leftSize;  // 这个值其实不用求也没关系，以后用不上

        // 3. 先创建根结点
        TreeNode root = new TreeNode(rootVal);

        // 4. 切出左子树的前序和中序序列
        List<Integer> leftPreorder = preorder.subList(1, 1 + leftSize); // 从前序中切左子树前序
        List<Integer> leftInorder = inorder.subList(0, leftSize);       // 从中序中切左子树中序
        // 使用相同的方式构建二叉树（左子树）：问题规模肯定变小了 (leftPreorder.size() < preorder.size())
        // 前序/中序序列的长度一定会收敛到 0（特殊情况）
        TreeNode left = build(leftPreorder, leftInorder);

        // 5. 切出右子树的前序和中序序列
        List<Integer> rightPreorder = preorder.subList(1 + leftSize, preorder.size());
        List<Integer> rightInorder = inorder.subList(leftSize + 1, inorder.size());
        TreeNode right = build(rightPreorder, rightInorder);

        // 6. 把左右子树和根结点产生关系
        root.left = left;
        root.right = right;

        // 7. 返回构建好的树
        return root;
    }
    //数组方法
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        // 利用 int[] array + int fromIndex + int toIndex
        // 数组，开始下标（含），结束下标（不含）  左闭右开
        // 来划定区间
        return build(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode build(int[] preorder, int pfrom, int pto, int[] inorder, int ifrom, int ito) {
        // size = pto - pfrom
        // 断言 pto - pfrom == ito - ifrom
        int size = pto - pfrom;
        if (size == 0) {
            return null;
        }

        // 1) 根的值是 前序区间的第一个元素（不是数组的第一个元素）
        int rootVal = preorder[pfrom];
        TreeNode root = new TreeNode(rootVal);

        // 2) 在中序区间中找到 rootVal 的下标
        int index = -1;
        for (int i = ifrom; i < ito; i++) {
            if (inorder[i] == rootVal) {
                index = i;
            }
        }
        // 断言 i != -1。因为根的值一定在中序序列的区间中
        // 这个时候的左子树结点个数 leftSize != index
        int leftSize = index - ifrom;

        // 3) 切出左子树的前/中序序序列区间，找到其开始下标和结束下标
        // 前序的开始和结束
        int leftPfrom = pfrom + 1;
        int leftPto = pfrom + 1 + leftSize;
        // 中序的开始和结束
        int leftIfrom = ifrom;
        int leftIto = ifrom + leftSize;
        // 构建左子树
        root.left = build(preorder, leftPfrom, leftPto, inorder, leftIfrom, leftIto);

        // 4) 切出右子树的前/中序区间
        // 前序
        int rightPfrom = pfrom + 1 + leftSize;
        int rightPto = pto;
        // 中序
        int rightIfrom = ifrom + leftSize + 1;
        int rightIto = ito;
        // 构建右子树
        root.right = build(preorder, rightPfrom, rightPto, inorder, rightIfrom, rightIto);

        // 返回构建好的树的根
        return root;
    }

    public static void main(String[] args) {
        int[] preorder = { 'A', 'B', 'D', 'E', 'F', 'C', 'G', 'H' };
        int[] inorder = { 'E', 'D', 'F', 'B', 'A', 'G', 'C', 'H' };

        Solution solution = new Solution();
        TreeNode root = solution.buildTree(preorder, inorder);
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}